The present invention relates to a graphic processing device and method in a field of computer graphics.
When a three-dimensional object is projected on a two-dimensional screen, an object partially or entirely shades other objects behind it. In order to obviate such an undesired phenomenon, a scan-line algorithm has been proposed which executes sequential processings using a general-purpose processor. A Z-buffer algorithm has been also proposed which is suitable to be implemented in hardware. The scan-line algorithm, when luminance data of each of pixels are displayed for each raster scan as in CRT, uses a very strong correlation between a pixel and adjacent pixels or a pixel on a subsequent scan line. Although this algorithm is suitable to execute sequential processings, it has a disadvantage of requiring a large number of calculations and complicating control logic. On the other hand, the Z-buffer algorithm previously stores for each of pixels the color and luminance (represented by the luminance) of a plane displayed on each pixel and the depth of the plane, and compares the depth of a new plane with the stored depth whenever the new plane is input; then only when the depth of the new plane is smaller than the stored depth, the stored depth is updated and also the luminance of the new plane is registered. Therefore, although the Z-buffer algorithm requires depth registers (generally called `Z-buffers`) to be provided for all the pixels and so a very large memory circuit, it has an advantage of comparatively simple control logic.
As an intermediate method of those hiddensurfaces elimination algorithms, a method using a correlation between scan lines and the Z-buffer algorithm within one scan line is disclosed in N. Gharachorloo and C. Pottole, "Super buffer: A systolic VLSI graphics engine for real time raster image generation", 1985 Chapel Hill Conference on Very Large Scale Integration, pp. 285-305. The hardware to implement this method, however, is too large so that it is difficult to realize the entire array in LSI.
The inventors of the present invention proposed a hidden-surface processing device disclosed in JP-A-62-100878 which is suitable to be realized in LSI with less hardware.
FIG. 8 is a system block diagram of the proposed hidden-surface processing device. FIG. 9 is a view showing the details of each of pixel processors which constitute the hidden-surface processing device. In FIGS. 8 and 9, 1 is a pixel processor corresponding to each of N pixels on one scan line; 10 is a depth register for registering the depth coordinate of a plane nearest to the screen in terms of pixel positions; 11 is a luminance register for registering the luminance information of the plane; and 12 is an adder for deciding whether or not the pixel processor is within a range where a plane segment is located, adding displacement in the depth, comparing depth data and adding a displacement in luminance data in a time division manner.
Referring to a conceptual view of FIG. 10, explanation will be made on the operation of the hidden-surface processing device thus constructed.
A plane 200 is defined in a three-dimensional space (generally called a normalized device coordinate system) as shown in FIG. 10 in which a depth coordinate, a z-coordinate is added to the x-y coordinate system corresponding to an M.times.N two-dimensional screen. The plane 200 is projected on the x-y plane to be displayed on the screen. With the raster-scan CRT, this processing is performed for each horizontal scan line so that it will be performed on the section 201 provided by cutting the plane 200 with a plane (generally called a scan line plane) passing the present scan line and in parallel to the x-z plane. This section 201 is called a plane segment. The individual plane segment has elements of a left end point coordinate (XL, ZL), the number of successive pixels (dX), a z-coordinate displacement for each pixel (Z'), luminance information I at the left end point, and a luminance displacement I' for each pixel. The token having these items of information is input in a manner divided into an A input port Ai and a B input port Bi to a left end pixel processor 1 of the pixel processors formed in an array as shown in FIG. 8. Control information CTRLi includes IN flag information indicative of that the corresponding pixel processor is within a range where the plane segment in question is located The information given to the respective ports in a time divisional manner are tabulated as shown in FIG. 11.
The operation of each pixel processor is as follows.
At a first timing T1, data at the A input port Ai and an all 1 pattern are supplied to an adder 12 to provide the subtraction result of the A input data minus 1. If the IN flag=0, and the subtraction result is negative, it means that the pixel processor has entered the range where the plane segment is located. Then, the data dX at the B input port Bi is shifted to the A port by the selector 14 to enter the latch 17. Also the IN flag is inverted to 1 to enter the latch 16. If the IN flag=1, and the subtraction result is negative, it means that the pixel processor has gone out from range where the plane is located. Then, the IN flag is inverted to 0 to output the negative value (the maximum value in integers with no sign) to the A output port as it is. In other cases, the CTRLi is output to CTRLo as it is and the addition result is output to the A output port Ao.
At a second timing T2, if the IN flag=1, Z at the A input port Ai and Z' at the B input port Bi are added to produce the addition result at the A output port Ao. If the IN flag=0, Z at Ai is output to Ao as it is without being updated.
At a third timing T3, Z at Ao at the timing T2 is held as it is. Then, with the IN flag=1, Z at Ai and Zb in the depth register 10 are compared by the adder 12. If the comparison result is Z&lt;Zb, Z at Ai will be stored in the depth register 10.
At a fourth timing T4, if the IN flag=1 and the above comparison result is Z&lt;Zb, I at the B input port Bi will be stored in the luminance register 11, and I at Ai and I; at Bi are added to produce the addition result at Ao. In other cases, I at Ai is output to Ao as it is without being updated.
At the above four all timings, the value at Bi is output at Bo as it is through the latch 18.
FIG. 12A shows the state where the token as described above flows along the array of pixel processors while being subjected to the processing by each pixel processor. Upon completion of processing all the tokens on one scan line, the luminance data of the segment nearest to the corresponding pixel positions is stored in the luminance register in each pixel processor.
The operation of each pixel processor for a sweep token will be explained which reads the contents of the luminance register of each pixel processor and initializes the contents of a depth register and the luminance register As understood from the above description, it is possible to insert, in the timing slot of T2 or T3 unused on the bus of the CTRL signal, a discriminator for discriminating whether the token is a plane segment or a sweep token At the first timing T1, the number DPR of displayed pixels on one scan line is received in place of X, and 1 is subtracted from it to count the remaining number of displayed pixels. Then, that the subtraction result is negative means that the token has deviated from the display range so that the IN flag is inverted to 0. At the second timing T2, if the token is within the display range with IN flag=1, the pixel processor 1 sends the data in the luminance register 11 to the luminance data bus. At the third timing T3, if the token is within the display range with IN flag=1, an initial value Z back is stored in the depth register 10. At the fourth timing T4, if the token is within the display range with IN flag=1, an initial value I back is stored in the luminance register 11.
FIG. 12B shows the state where the sweep token as described above flows along the array of pixel processors while being subjected to the processing by each pixel processor. In this way, the luminance data of the segment nearest to the pixels on one scan line are successively read out from each pixel processor.
Meanwhile, the conventional anti-aliasing algorithm along a scan line is disclosed in e.g. `COMPUTER GRAPHICS` by E. Nakamae, edited by DENSITSUSIN GAKKAI, 1987, PP. 183-186.
This anti-aliasing algorithm will be explained below.
If the x coordinate of a boundary of a plane segment has a minimum value XMIN and a maximum value XMAX within the same pixel as shown in FIG. 13A, the shaded portion is a trapezoid. Then, the luminance of the pixel is corrected by the rule X0*IL+(1-X0)*IR, assuming that the luminance in the shaded portion of the pixel is IR and that in the remaining left portion is IL, and the width X0 of the remaining portion on the X central line is X0 of the pixel. Further, if the boundary of the plane segment extends over some pixels as shown in FIG. 13B, the luminance of each of the intermediate pixels is corrected by the rule of Yn*lL+(1-Yn)*IR(n=0, 1, 2, . . . ) assuming that the width of the remaining portion on the Y central line of each of the intermediate pixels is Y0, Y1, Y2 . . . Yn; this is also because the shaded portions in the intermediate pixels other than the pixels at both ends are trapezoids. The luminance of the first and the last pixel can be corrected on the basis of that they include a triangle and a pentagon (a triangle or trapenzoid as the case may be). Otherwise, it can be defined as IL or IR admitting some error.
The hidden-surface processing device having the constructions as mentioned above has a disadvantage that the processing using error data such as antialiasing cannot be performed using only the data directly obtained from the device.
The above anti-aliasing method requires decision relative to XMIN and XMAX, and also requires to calculate Y0, Y1 and Y2 if the boundary of the plane segment extends over plural pixels as shown in FIG. 13B; this calculation is time-consuming and so is difficult to carry out in real time. Further, if the data corresponding to one scan line are successively output, it is necessary to once store the data somewhere for the anti-aliasing processing. Further, the graphic display device in which the luminance is omitted in its decimals generates the state as shown in FIG. 14. Specifically, up to the pixel A is painted for boundary 1 while up to the pixel B is painted for boundary 2. In this case, if the aliasing is removed by the above conventional anti-aliasing method, the luminance of the pixel A can be corrected at the boundary 1 and that of the pixel C can be corrected for the boundary 2. The corrected color for the pixel B, however, cannot be decided unless the color before drawing the boundary 2 is held.